1. Field of the Invention
The present invention relates to an error propagation path extraction system, error propagation path extraction method, and a recording medium recording error propagation path extraction control program, particularly to an error propagation path extraction system for quickly obtaining a signal line in which a fault may propagate in a combinational logic circuit.
2. Description of the Related Art
In the case of a conventional error propagation path extraction system, there is a system for extracting a route in which an error may propagate in a circuit when an input/output logical state obtained by inputting a test pattern is different from a normal output expected for a normal circuit. As disclosed in the official gazette of Japanese Patent Application Laid-Open No. 8-146093, this system can be used as a part of a fault diagnosis system of a sequential circuit. In this case, a fault can be present in the combinational circuit or an error can be included in an input pattern.
As the above error propagation path extraction system, there is a inverse logical inference system using a back track system introducing Don't Care. This inverse logical inference system is a system for estimating the logical state of the input terminal of a combinational logic circuit from the logical state of the output terminal of the circuit.
When using the fault diagnosis system for the fault analysis of a 100K-gate-size sequential circuit, a combinational circuit to be extracted is estimated as a 10K-gate size and the capacity for estimating every input signal pattern of the same-size combinational circuit is necessary.
In this case, a back track system is a system for estimating the logical state of every signal line by repeating implication and decision, which is also referred to as a "branch-and-bound system."
Because the back track system uses only a small number of memories, in which the number of data values is proportional to the number of gates, it has features that it is possible to easily estimate the number of memories used, the algorithm is simple, and parallel processing is easy. In the case of the back track system, however, when a circuit size increases, the decision frequency increases. Therefore, a lot of calculation time is required to obtain every input logical state.
By applying the back track system to inverse logical inference, it is possible to estimate the internal logical state of a logic circuit. The back track system is described in "M. Abramobvici, M. A. Breuer, and A. D. Friedman, Digital Systems Testing and Testable Design, IEEE Press, New York, pp. 186-196, 1990."
The above error propagation path extraction system is a method for comparing the input estimated state obtained through inverse logical inference and the logical state in a combinational logic circuit obtained in the process of the inverse logical inference with a normal logical value previously obtained through logical simulation in a normal circuit, recognizing a signal line under a faulty state, and extracting an error propagation path. This method makes it possible to obtain every input logical state meeting an output logical state and every internal logical state of a circuit and extract an error propagation path by comparing the states with a normal logical value.
However, it is estimated that the decision frequency greatly increases and the calculation time increases in the case of a multiplier. Moreover, as a circuit increases in size, the number of input logical states becomes tremendous. If an error propagation path is extracted from these tremendous logical states, a route not influencing a fault output is also extracted. In this case, a route not influencing a fault output denotes a route not propagating a fault to a fault output even if the fault occurs on the route though a logical state does not coincide with a normal logical value.
Moreover, to obtain an input logical state meeting an output logical state, it is assumed that a combinational circuit is normal. Therefore, it is impossible to extract an error propagation path for a fault due to the inside of the combinational circuit.
An embodiment of the prior art is described below in detail by referring to the accompanying drawings. In FIG. 10, the embodiment of the prior art includes an input unit 1 such as a keyboard, a data processor 2 operated in accordance with program control, a memory 4 for storing information, and an output unit 5 such as a display or printer.
The memory 4 is provided with a logic-circuit-structure storage section 41, a decision-state storage section 42, and a logical-state storage section 43. The logic-circuit-structure storage section 41 previously stores the structure of a logic circuit, that is, the type of gate, connective relation between gates, connective relation between gate and signal line, and connective relation between signal lines.
The decision-state storage section 42 stores a decision level showing the number of decisions performed and a decision level when the logical state of each signal line is estimated through implication. The logical-state storage section 43 stores the logical state of each signal line under processing and the logical state (normal logical value) of each signal line when a circuit is normal.
The data processor 2 is provided with an initialization section 21, an X(Don't Care) state (hereafter referred to as X state) setting section 22, a first implication section 23, a logical contradiction judgment section 24, a processing-completion judgment section 25, a back-track section 26, U(Unknown)-state (hereafter referred to as U state) retrieval section 27, logical-value decision section 29, and logical-value comparison section 30.
The initialization section 21 sets the type of a logic circuit supplied from the input unit 1 and the logical state of an input/output terminal. The X-state setting section 22 refers to a logic circuit structure stored in the logic-circuit-structure storage section 41 and the logical state of each signal line stored in the logical-state storage section 43, sets the initial logical state of each signal line whose logical state is not fixed to X state, and records the X state in the logical-state storage section 43. In this case, the X state is a logical state representing to allow both logical states "0" and "1" when both logical states "0" and "1" of a signal line do not contradict the logical state of the entire logic circuit.
As shown in FIG. 11, the first implication section 23 includes an implication section 231, logical contradiction detection section 232, a first-implication-allowing-gate retrieval section 233, and an implication-completion judgment section 234.
The implication section 231 refers to a logic circuit structure stored in the logic-circuit-structure storage section 41 and the logical state of each signal line stored in the logical-state storage section 43 and estimates the logical state of an input/output line at an input/output line set by the initialization section 21, a gate connected to a signal line decided by the logical-value decision section 29, or a gate detected by the first implication-allowing-gate retrieval section 233. Estimation of a logical state is performed by using "0," "1," and "X."
When a new logical value is estimated, the implication section 231 records the logical value in the logical-state storage section 43 and moreover, records a decision level showing under what number of decisions the estimation is performed in the decision-state storage section 42.
The logical-contradiction detection section 232 refers to a logic circuit structure stored in the logic-circuit-structure storage section 41 and the logical state of each signal line stored in the logical-state storage section 43 and detects a contradiction between a new logical state decided by the implication section 231 and a logical state having been decided by that point of time if any.
The first implication-allowing-gate retrieval section 233 refers to a logic circuit structure stored in the logic-circuit-structure storage section 41 and the logical state of each signal line stored in the logical-state storage section 43 and retrieves an implication-allowing gate. The implication-enable gate is a gate capable of implicating and deciding the logical state of an input/output line which is connected to a gate and whose logical state is not decided yet in accordance with the function of the gate and the logical state of an input/output line which is connected to the gate and whose logical state is already decided as "0" or "1."
The implication-completion judgment section 234 judges that every implication is completed and completes the processing of the first implication section 23 when a gate for implication is not detected by the first implication-allowing-gate retrieval section 233.
The logical-contradiction judgment section 24 detects whether a contradiction occurs in the logical state of a signal line in the first implication section 23. The processing-completion judgment section 25 refers to the logical state of each signal line stored in the logical-state storage section 43 and judges whether the logical state of every signal line is estimated.
The back-track section 26 refers to a decision state stored in the decision-state storage section 42 and the logical state of a signal line stored in the logical-state storage section 43, erases a logical state at a decision level whose processing is already completed, and returns the logical state of each signal line to the logical state before decision is performed. The U-state retrieval section 27 checks the logical state of input/output of the gate in the combinational circuit and retrieves a signal line whose logical state is incomplete and which is under an Unknown state.
The logical-value decision section 29 decides the logical state of a signal line whose logical value detected by the U-state retrieval section 27 is an indefinite "U" state. The logical-value comparison section 30 compares the obtained logical state of each signal line with a normal logical value showing the logical state of each signal line obtained through logical simulation by a normal circuit, extracts an error propagation path, and outputs the data for the route to the output unit 5.
Then, operations of the embodiment of the prior art are described below by referring to FIGS. 10 to 14. The logical state "U (Unknown)" denotes an indefinite state in which the logical state of a signal line cannot be decided as "0" or "1." However, the logical state "X (Don't Care)" denotes a logical state allowing both logical states "0" and "1" of a signal line when the both logical states "0" and "1" of the signal line don not contradict the logical state of the entire logic circuit.
The logical state of an input/output terminal supplied from the input unit 1 is set by the initialization section 21 to initialize a decision level (dlevel) showing the decision frequency (steps S51 and S52 in FIG. 12). The state "X" is set to a signal line whose logical state is not estimated as the initial state for implication. The result is stored in the logical state storage section 43 (step S53 in FIG. 12).
Then, implication is performed by the first implication section 23 (step S54 in FIG. 12). The implication is an operation for estimating the logical state of an input/output line of a gate not estimated yet in accordance with the logical state of the input/output line of a gate already estimated at each gate.
First, the implication section 231 (step S71 in FIG. 13) estimates the logical state of an input/output line through implication at a detected gate. The logical state of an input/output line is estimated at an input/output line set through initialization (step S51 in FIG. 12), a gate connected to a signal line decided by logical-value decision section 29, or a gate detected by the first implication-allowing-gate retrieval section 233. The estimated logical state is recorded together with the decision level at that point of time. FIG. 14 shows an example of implication in the case of a two-input NAND gate.
The logical-contradiction detection section 232 detects whether a contradiction occurs in a newly-decided logical state. When the section 232 detects a contradiction, it completes implication (step S72 in FIG. 13). When a logical contradiction is not detected in step S72, the first implication-allowing-gate retrieval section 233 (step S73 in FIG. 13) retrieves other implication-allowing gate.
Then, the implication-completion judgment section 234 judges whether every implication is completed. When a gate is detected in step S73, the section 234 judges in step S74 that implication is not completed yet. When a gate is not detected in step S73, the section 234 judges in step S74 that implication is completed and completes first implication.
The logical-contradiction judgment section 24 detects the contradiction of the logical state of each signal line under implication (step S55 in FIG. 12). Unless a contradiction is detected by the logical-contradiction judgment section 24, the processing-completion judgment section 25 refers to the logical state of a signal line stored in the logical-state storage section 43 and judges whether the logical state of every signal line is estimated as "0," "1," or "X" (step S56 in FIG. 12).
The section 25 judges in step S56 that logical state estimation of every signal line is not completed, the U-state retrieval section 27 checks the logical state of input/output of the gate in the combinational circuit and retrieves an Unknown-state signal line whose logical state is incomplete (step S57 in FIG. 12). A detected signal line is decided as "0," a decision level (dlevel) showing the decision frequency is increased by 1 (step S58 in FIG. 12), and implication is restarted by the first implication section 23 (step S54 in FIG. 12).
When it is decided by the processing-completion judgment section 25 that the logical state of every signal line is estimated, the logical-value comparison section 30 (step S59 in FIG. 12) extracts a signal line having a state different from a normal logical value, that is, an error propagation path because the logical state in a circuit is decided as "0," "1," or "X."
Then, the section 25 judges whether decision processings for both "0" and "1" are completed for every decided line (step S60 in FIG. 12). When it is judged in step S60 that the logical state of every signal line is estimated, the logical state of a signal line in the combinational circuit is estimated as "0," "1," or "X." Also when a contradiction is detected by the logical-contradiction judgment section 24, the judgment processing in step S60 is performed.
When the processing-completion judgment section 25 (step S60 in FIG. 12) judges that decision processing is not completed, the back track section 26 retrieves the state "1" and a decision line not decided and having the highest decision level, initializes the detected decision line to the state "U" showing that the logical state of a signal line estimated at a decision level equal to or higher than the decision level of the detected signal line is under an indefinite state, and returns the logical state of each signal line to the logical state before the decision is performed (step S61 in FIG. 12).
The logical-value decision means 29 decides the state of the decision line detected by the back-track means 26 as "1" (step S62 in FIG. 12) and returns to the implication processing by the first implication section 23 (step S54 in FIG. 12). When it is judged by the processing-completion judgment section 25 (step S60 in FIG. 12) that decision processing is completed, error propagation path extraction processing is completed.
FIG. 15 shows a decision tree structure when applying an error propagation path extraction system of the prior art to the ISCAS'-85 (The 1985 IEEE International Symposium on Circuits and Systems) benchmark circuit C17 (see FIG. 3). In FIG. 15, the logical state (output vector) of an output terminal is assumed as line 22 (122)=1 and line 23 (123)=1.
A decision tree structure shows a signal line number for a node (numeral enclosed by a circle; 1, 3, 10, or 16 in FIG. 15) to perform decision and a branch (continuous line connecting nodes) shows a decided logical state. In the case of FIG. 15, by performing decisions of both "0" and "1" for a total of four signal lines eight times, five internal logical states meeting the logical state of the output terminal are obtained and an error propagation path is obtained by comparing each state with a normal logical value.
In FIG. 15, logical states of the signal lines shown by rectangular frames are shown in the sequence of line 1, line 2, line 3, line 6, line 7, line 10, line 11, line 16, line 19, line 22, and line 23. Moreover, an underlined logical state shows an error propagation path different from a normal logical value.
In this case, from the circuit diagram in FIG. 3, it is found that line 1 (11) and line 10 (110), when a fault occurs on the signal lines, have no possibility of propagating the fault to line 23 (123).
As the result of comparing five obtained logical states, (1110X010X11) and (0110X110X11) are different from each other in the logical states of line 1 and line 10 and (010XX110X11) and (110XX110X11) are different from each other only in the error of line 1 and redundant data including line 1 and line 10 having no possibility of propagating an error to a failing output terminal is output.
As other error propagation path extraction method, there is a fault dictionary method of comparing a fault dictionary previously obtained through a fault simulation with a test result and estimating a fault portion. However, preparation of a fault dictionary requires a fault simulation requiring a long calculation time and moreover, the dictionary size increases as a circuit size increases. Therefore, it is general that the type of fault is restricted to a single fault.
The art disclosed in the official gazette of Japanese Patent Application Laid-Open No. 1-244384 shows an apparatus for specifying a fault portion by following an error propagation path while measuring the logical state of a signal line from a failing output terminal in accordance with physical analysis means such as an EB (electron beam) tester.
Recently, however, an LSI (large scale integrated circuit) chip has been decreased in size and wiring has been formed to be a multilayer. Therefore, it is difficult to measure the logical state in a circuit with physical means and thus physically follow an error propagation path.
In the case of the above conventional error propagation path extraction method, the computational complexity increases and thereby, the computational time increases because decision and implication are executed also for a signal line not connected with an error propagation path.
Because it is the original object of test pattern generation to obtain an input pattern allowing an error assumed in a circuit to propagate to an output terminal and be detected, the test pattern generation is optimized so as to obtain one input pattern at a high speed. Therefore, to obtain every error propagation path meeting an output logical state, a lot of computational time is required and similarly to the case of the above prior art, it is difficult to extract only an error propagation path influencing a failing output terminal and thus, the amount of output data greatly increases.
Moreover, because an error propagation path having no possibility of propagating an error is output to a fault output, the amount of data to be output greatly increases. Furthermore, because an input logical state meeting an output logical state is obtained by using the inverse logical inference system and assuming a combinational circuit to be normal and thereafter, an error propagation path is output, it is impossible to extract an error propagation path due to a fault in the combinational circuit.